package SingleLinkedList;

import java.util.HashMap;

public class CopyListWithRandom {
    public static class Node {
        public int value;
        public Node next;
        public Node rand;

        public Node(int value) {
            this.value = value;
        }
    }

    public static Node copyListWithRand1(Node head) {
        HashMap<Node, Node> map = new HashMap<>();

        Node cur = head;

        // 将单链表的节点一个个copy后放到map中
        while (cur != null) {
            map.put(cur, new Node(cur.value));
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            // cur 老
            // map.get(cur) 新
            map.get(cur).next = map.get(cur.next);
            map.get(cur).rand = map.get(cur.rand);
            cur = cur.next;
        }

        return map.get(head);
    }

    public static Node copyListWithRand2(Node head) {
        if (head == null) {
            return null;
        }

        Node cur = head;
        Node next;

        // copy node and link to every node
        // 1 -> 2
        // 1 -> 1' -> 2 -> 2'
        while (cur != null) {
            // 记录原来的下一个
            next = cur.next;
            // 下一个变成自己的复制品
            cur.next = new Node(cur.value);
            // 复制品的下一个是原来的下一个
            cur.next.next = next;
            // 下一个需要处理的是原来的下一个
            cur = next;
        }
        cur = head;
        Node curCopy;

        // set copy node rand
        // 1 -> 1' -> 2 -> 2'
        while (cur != null) {
            // 真正的下一个是下下一个
            next = cur.next.next;
            // 下一个是对应的克隆节点
            curCopy = cur.next;
            // 设置克隆节点的rand 节点
            curCopy.rand = cur.rand != null ? cur.rand.next : null;
            // 下一个需要处理的是原来的下一个
            cur = next;
        }

        Node res = head.next;
        cur = head;
        // split
        while (cur != null) {
            // 真正的下一个是下下一个
            next = cur.next.next;
            // 下一个是对应的克隆节点
            curCopy = cur.next;
            // 还原回真正的对应关系
            cur.next = next;
            curCopy.next = next != null ? next.next : null;
            // 下一个需要处理的是原来的下一个
            cur = next;
        }

        // 返回新copy出的链表的头节点
        return res;
    }
}
